#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int a,b,c;
    cin>>a>>b>>c;
    while(c)
    {
        int x=b-(a%b);
        if(c>=x)
        {
            c-=x;
            a+=x;
            while(a%b==0)a/=b;
        }
        else a+=c,c=0;
        if(a==1)c%=b-1;
    }
    cout<<a<<endl;
}
signed main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--)
    {
       solve();
    }
    return 0;
}